1. Field
The present application relates to the operational performance of a database, particularly its performance when the contents of the database are being altered. The present application has one, but not its only, application to a relational database, and more particularly a directory services database. In a further form, the invention relates to the performance of a database utilized in providing directory services. The invention, however, should not be limited to only this application.
2. Description of the Related Art
A part of the problem which the present invention seeks to address, stems from a known situation in databases called “database isolation levels”. Isolation levels allow a user to specify an appropriate compromise between consistency and concurrency. This feature makes it possible to increase concurrency when the consistency and accuracy of the data is not essential.
Many databases support four isolation levels as defined by the ANSI/ISO SQL92 standard. These levels are Read Uncommitted (RU), Read Committed (RC), Repeatable Read (RR) and Serializable.
The highest degree of isolation is called “Serializable”, since the concurrent execution of serializable transactions is equivalent to a serial execution of the transactions. The Serializable level offers the highest degree of protection to the application programmer, i.e., high isolation. However, such high isolation often results in a lower degree of concurrency. At lower degrees of isolation, more transactions may run concurrently, but it can also introduce some inconsistencies in the data. The ANSI/ISO SQL92 standard identifies three inconsistencies that can occur during the execution of concurrent transaction:
1. “Dirty read”: A transaction T1 modifies a row. A transaction T2 then reads that row before T1 performs a COMMIT. If T1 then performs a ROLLBACK, T2 will have read a row that was never committed and that may thus be considered to have never existed.
2. “Non-repeatable read”: A transaction T1 reads a row. A transaction T2 then modifies or deletes that row and performs a COMMIT. If T1 then attempts to reread that row, it may receive the modified value or discover that the row has been deleted.
3. “Phantom rows”: A transaction T1 reads a set of rows N that satisfy some <search condition>. A transaction T2 then executes SQL statements (or instructions) that generate one or more rows that satisfy the <search condition> used by transaction T1. If transaction T1 then repeats the initial read with the same <search condition>, it obtains a different collection of rows.
Table I below shows how the ANSI/ISO SQL92 standard defines which inconsistencies are possible (Yes) and which are not (No) for a given isolation level.
TABLE IDirtyNon-repeatablePhantomReadReadrowsREAD UNCOMMITTEDYesYesYesREAD COMMITTEDNoYesYesREPEATABLE READNoNoYesSERIALIZABLENoNoNo
Thus it can be seen that the “Serializable” level provides the highest isolation and the least possibility of inconsistencies, but, as noted above, this often results in the lowest level of performance. Conversely, the “read uncommitted” level which provides the lowest isolation and the highest possibility of inconsistencies, often results in the highest level of performance.
One reason isolation levels are an issue can be illustrated as follows. When using a database, there may be one user wanting to update a row and another user wanting to read the same row. Depending on the isolation level selected, a database may lock a row when a row is being updated and thus the row cannot be read. This may not seem to be a major problem with only one user, but when there are many users, even thousands of users wanting to read a database, such a ‘lock’ is found to be extremely wasteful of a users time. If the update takes a long time, this only exacerbates the problem of delaying the read by the other users.
One way around this problem is to allow reads and updates to go on concurrently, by selecting a lower isolation level. But this then leads to other problems. If the read is not locked during an update, the read function may be a “dirty read” on what is called a “dirty page” i.e. something may be read that is in the middle of being changed. To illustrate this problem, imagine in a payroll database, a first application is going through the database and increasing every payroll entry by 10%, while concurrently a second application is reading the database. If the first application had updated half the database entries and the second application had read all the database entries and had performed a sum operation to check the validity of the read, it would be found to be neither pre-value nor post-value. In essence, half the database had been updated by 10% and the other half would not yet have been updated by 10% at the time the read operation occurred. So, in that particular instance, it may be considered more appropriate to run at a higher isolation level, but then again the performance or speed of a read will be reduced if the read is conducted at the higher isolation level.
In a directory services environment, which is usually a database/application that requires relatively high performance, the database/application deals with ‘objects’ and a metadata design. The directory system can be set at a relatively low isolation level in order to improve performance. But at the lower isolation levels, as illustrated above, the ‘dirty read’ problem can exist. The design of some directory systems utilize a table structure which includes, in effect, ‘in’ tables and ‘out’ tables. FIG. 1 illustrates this.
The idea behind using an ‘in’ table and ‘out’ table structure, is that a search can be conducted on an ‘in’ table, a search table for example, and the results of that search can be based on an ‘out’ table, an entry table for example. In FIG. 1, lets say a search for Rick is called for. A search will find that Rick is entry No. 123 and then the result, from the entry table, is read from entry 123 together with the stored information associated with that entry.
Information in these tables may be included by adding rows to the search table, to the entry table and to other selected tables. The information may also be stored in a raw form and/or a normalized form. However, if before the process of adding rows is completed, a read is performed not all the information that is being added to the entry table would be returned because not all the information had yet been added. This is what is referred to as a ‘partial entry on add effect’ and it manifests itself in that some (not all) of the added information may appear in results of a read. If this occurs, the read information is only partially correct. Conversely, there is also what is called a ‘partial entry on remove effect’, where during a remove operation in which rows are being removed from tables, a search is performed before this removal operation is complete. The information returned from the search may not include information that has been deleted (or information that will be deleted very shortly after the search). Similarly there is what is called a ‘partial entry on modify effect’ which is in effect a combination of add and remove operations as outlined above, where either attributes of a particular entry in a database are added or removed.
What is described above, is an effect that can otherwise be referred to as an ‘update’ problem, or a partial entry problem. There is yet another problem in the prior art, in what may be called a partial entry replication problem. This partial entry replication problem stems from the situation where there are two independent systems that are being replicated using a database replication technique. In such a replication environment, it is desirable to replicate anything that happens on a ‘master’ database system on one or more ‘slave’ database systems. So when an entry which has been added, deleted or modified on the master database system it is desirable to also replicate any add, remove or modify operations on the slave database systems.
One reason this partial entry replication is considered a problem, is that an update may be fast on the ‘master’ database system, but is typically considerably slower when replicating on the slave database systems. Thus, instead of taking milliseconds this replication may take seconds, depending on network traffic and the system configuration. With such delays, the partial entry replication problem can become quite noticeable to a user. Again, the problem is exacerbated if many updates are being done concurrently, which may be the case in a relatively large database.